Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

A sequential scheduling problem with impatient jobs

There are n customers that need to be served. Customer i will only wait in queue for an exponentially distributed time with rate λ_i before departing the system. The service time of customer i has distribution F_i, and on completion of service of customer i a positive reward r_i is earned. There is a single server and the problem is to choose, after each service completion, which currently in queue customer to serve next so as to maximize the expected total return. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 659–663, 2015     

面向应急管理计算实验的模型构建和模型管理

基于人工社会的计算实验使应急管理的定量分析与研究成为可能。然而,应急管理模型涉及多个学科与领域,具有多层次、非线性和多粒度等特点,需要一套规范的流程来指导人工社会的模型建立和模型管理。论文梳理了面向应急管理的模型体系,提出了基于领域特定建模的人工社会建模方法,解决了多领域建模问题;研究了模型的形式化描述与编码问题,并实现了模型的有效管理;结合"甲型H1N1"病程模型,详细论述了模型的构建方法与管理问题,为面向应急管理的计算实验提供一体化的模型服务。     

全面深化改革 实现我国社会主义市场经济地位的转变

党的十八届三中全会的最大亮点和理论创新之一就是,提出了要实现市场对资源配置的决定性作用。这是思想解放的重大突破,也是深化经济体制改革以及引领其他领域改革的基本方针。阐述了改革开放35年党对市场经济地位和作用认识的历史进程,以及我国社会主义市场经济地位转变的必然性,提出了全面深化经济体制改革、实现市场经济地位转变的举措。     

Single machine just‐in‐time scheduling problems with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs to be processed and his own objective function, and both share a common processor. In the single‐machine problem studied in this article, the goal is to find a joint schedule that minimizes the total deviation of the job completion times of the first agent from a common due‐date, subject to an upper bound on the maximum deviation of job completion times of the second agent. The problem is shown to be NP‐hard even for a nonrestrictive due‐date, and a pseudopolynomial dynamic program is introduced and tested numerically. For the case of a restrictive due‐date (a sufficiently small due‐date that may restrict the number of early jobs), a faster pseudopolynomial dynamic program is presented. We also study the multiagent case, which is proved to be strongly NP‐hard. A simple heuristic for this case is introduced, which is tested numerically against a lower bound, obtained by extending the dynamic programming algorithm. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 1–16, 2014     

Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria

We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive‐repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date‐related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Flow shop scheduling with earliness,tardiness, and intermediate inventory holding costs

We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding), and intermediate (work‐in‐process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two different, but closely related, Dantzig‐Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig‐Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near‐optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with different types of strongly ????‐hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near‐optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

灾害应急反应建模与仿真

为了满足多智能体应急反应仿真的需求,首先对构建多智能体应急反应仿真模拟框架的复杂性进行了分析,在此基础上提出并设计了组件式仿真模拟框架.采用本体(Ontology)建模、语义网模型及产生式规则推理等理论方法构建了仿真模拟框架的场景建模模块、人员Agent建模模块等组件.最后对依照上述研究内容所开发的原型系统进行了测试,对测试结果进行了分析,结果表明该框架能够有效满足多智能体应急反应仿真的建模需求.     

Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment

The ability to cope with uncertainty in dynamic scheduling environments is becoming an increasingly important issue. In such environments, any disruption in the production schedule will translate into a disturbance of the plans for several external activities as well. Hence, from a practical point of view, deviations between the planned and realized schedules are to be avoided as much as possible. The term stability refers to this concern. We propose a proactive approach to generate efficient and stable schedules for a job shop subject to processing time variability and random machine breakdowns. In our approach, efficiency is measured by the makespan, and the stability measure is the sum of the variances of the realized completion times. Because the calculation of the original measure is mathematically intractable, we develop a surrogate stability measure. The version of the problem with the surrogate stability measure is proven to be NP‐hard, even without machine breakdowns; a branch‐and‐bound algorithm is developed for this problem variant. A tabu search algorithm is proposed to handle larger instances of the problem with machine breakdowns. The results of extensive computational experiments indicate that the proposed algorithms are quite promising in performance. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

武警部队远程教育培训探讨

针对武警部队集中学习相对困难的情况,对当前远程教育培训模式进行了探讨,分析了远程教育中的资源建设问题,并以《汽车构造》课程为例进行了网络课程的开发,为武警部队培养高素质的现代官兵队伍提供有益参考。